package leetcode.editor.cn;

import java.util.*;

public class P399EvaluateDivision {
    public static void main(String[] args) {
        Solution solution = new P399EvaluateDivision().new Solution();
        String[][] equations = new String[][]{{"x1", "x2"}};
        List equationList = new ArrayList();
        for (String[] equation : equations) {
            equationList.add(new ArrayList<>(Arrays.asList(equation)));
        }
        double[] values = new double[]{3};
        String[][] queries = new String[][]{{"x2", "x1"}};
        List queriesList = new ArrayList();
        for (String[] equation : queries) {
            queriesList.add(new ArrayList<>(Arrays.asList(equation)));
        }
        for (double v : solution.calcEquation(equationList, values, queriesList)) {
            System.out.print("#" + v + "#");
        }
        System.out.println();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        class Node {
            String pre;
            String next;
            Double value;
            Integer index;
            boolean reverse;

            public Node() {
            }

            public Node(String pre, String next, Double value) {
                this.pre = pre;
                this.next = next;
                this.value = value;
            }

            public Node(String pre, String next, Double value, boolean reverse) {
                this.pre = pre;
                this.next = next;
                this.value = value;
                this.reverse = reverse;
            }

            public String getPre() {
                return pre;
            }

            public Double getValue() {
                return value;
            }

            public void setValue(Double value) {
                this.value = value;
            }

            public void setPre(String pre) {
                this.pre = pre;
            }

            public String getNext() {
                return next;
            }

            public void setNext(String next) {
                this.next = next;
            }

            @Override
            public boolean equals(Object o) {
                Node node = (Node) o;
                return Objects.equals(pre, node.pre) && Objects.equals(next, node.next);
            }

            @Override
            public int hashCode() {
                return pre.hashCode() + next.hashCode();
            }

            public Boolean isConnected(Node node) {
                if (this.pre == node.pre) {
                    return true;
                }
                if (this.next == node.next) {
                    return true;
                }
                if (this.pre == node.next) {
                    return true;
                }
                if (this.next == node.pre) {
                    return true;
                }
                return false;
            }

            public Boolean connect(Node node) {
                if (this.next == node.pre) {
                    return true;
                }
                return false;
            }

            public List<Node> sameNode(Node node) {
                List<Node> list = new ArrayList<>();
                if (this.pre == node.pre) {
                    double newValue1 = this.value * (1 / node.value);
                    double newValue2 = node.value * (1 / this.value);
                    Node newNode1 = new Node(node.next, this.next, newValue1);
                    Node newNode2 = new Node(this.next, node.next, newValue2);
                    list.add(newNode1);
                    list.add(newNode2);
                } else if (this.next == node.next) {
                    double newValue1 = this.value * (1 / node.value);
                    double newValue2 = node.value * (1 / this.value);
                    Node newNode1 = new Node(this.pre, node.pre, newValue1);
                    Node newNode2 = new Node(node.pre, this.pre, newValue2);
                    list.add(newNode1);
                    list.add(newNode2);
                } else if (this.pre == node.next) {
                    double newValue1 = this.value * node.value;
                    Node newNode1 = new Node(node.pre, this.next, newValue1);
                    double newValue2 = 1 / (this.value * node.value);
                    Node newNode2 = new Node(this.next, node.pre, newValue2);
                    list.add(newNode1);
                    list.add(newNode2);
                } else if (this.next == node.pre) {
                    double newValue1 = this.value * node.value;
                    Node newNode1 = new Node(this.pre, node.next, newValue1);
                    list.add(newNode1);
                    double newValue2 = 1 / (this.value * node.value);
                    Node newNode2 = new Node(node.next, this.pre, newValue2);
                    list.add(newNode2);
                }
                return list;
            }
        }

        public double[] calcEquationDFS(List<List<String>> equations, double[] values, List<List<String>> queries) {
            double[] newArr = new double[queries.size()];
            int size = equations.size();
            Map<String, List<Node>> nodeMap = new HashMap<>();
            for (int i = 0; i < size; i++) {
                List<String> arr = equations.get(i);
                double value = values[i];
                String pre = arr.get(0);
                String next = arr.get(1);
                Node node = new Node(pre, next, value);
                Node node1 = new Node(next, pre, value, true);
                nodeMap.compute(pre, (s, nodes) -> {
                    if (nodes == null) {
                        nodes = new ArrayList<>();
                    }
                    nodes.add(node);
                    return nodes;
                });
                nodeMap.compute(next, (s, nodes) -> {
                    if (nodes == null) {
                        nodes = new ArrayList<>();
                    }
                    nodes.add(node1);
                    return nodes;
                });
            }
            Set<String> find = new HashSet<>();
            for (int i = 0; i < queries.size(); i++) {
                List<String> arr = queries.get(i);
                String pre = arr.get(0);
                String next = arr.get(1);
                newArr[i] = -1.0;
                if (!nodeMap.containsKey(pre) || !nodeMap.containsKey(next)) {
                    continue;
                }
                LinkedList<Node> path = new LinkedList<>();
                List<Node> nodes = nodeMap.get(pre);
                for (Node node : nodes) {
                    path.push(node);
                }
                while (!path.isEmpty()) {
                    Node top = path.peek();
                    if (top.next == next) {
                        double val = 1;
                        while (!path.isEmpty()) {
                            Node poll1 = path.pop();
                            val *= poll1.reverse ? (1 / poll1.getValue()) : poll1.getValue();
                            while (!path.isEmpty() && !path.peek().connect(poll1)) {
                                path.pop();
                            }
                        }
                        newArr[i] = val;
                        break;
                    } else {
                        List<Node> nodeList = nodeMap.get(top.next);
                        boolean findValid = false;
                        for (Node node : nodeList) {
                            {
                                if (!find.contains(node.next)) {
                                    path.push(node);
                                    find.add(node.next);
                                    findValid = true;
                                }
                            }
                        }
                        if (!findValid) {
                            path.pop();
                        }
                    }
                }
            }
            return newArr;
        }

        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            double[] newArr = new double[queries.size()];
            int size = equations.size();
            Map<String, Integer> nodeMap = new HashMap<>();
            int id = 0;
            UF uf = new UF(equations.size() * 2);
            for (int i = 0; i < size; i++) {
                List<String> equation = equations.get(i);
                String a = equation.get(0);
                String b = equation.get(1);
                double value = values[i];
                if (!nodeMap.containsKey(a)) {
                    nodeMap.put(a, id);
                    id++;
                }
                if (!nodeMap.containsKey(b)) {
                    nodeMap.put(b, id);
                    id++;
                }
                Integer id1 = nodeMap.get(a);
                Integer id2 = nodeMap.get(b);
                uf.union(id1, id2, value);
            }
            for (int i = 0; i < queries.size(); i++) {
                List<String> list = queries.get(i);
                String a = list.get(0);
                String b = list.get(1);
                if (!nodeMap.containsKey(a) || !nodeMap.containsKey(b)) {
                    newArr[i] = -1;
                    continue;
                }
                newArr[i] = uf.isConnected(nodeMap.get(a), nodeMap.get(b));
            }
            return newArr;
        }

        class UF {
            private Integer[] parent;
            private Double[] weight;

            public UF(Integer len) {
                parent = new Integer[len];
                weight = new Double[len];
                for (int i = 0; i < len; i++) {
                    parent[i] = i;
                    weight[i] = 1.0;
                }
            }

            public Double isConnected(int v, int w) {
                Integer rootP = findParent(v);
                Integer rooQ = findParent(w);
                if (rootP == rooQ) {
                    return weight[v] / weight[w];
                } else {
                    return -1.0;
                }

            }

//          {"x1", "x2"}, {"x2", "x3"}, {"x3", "x4"}, {"x4", "x5"}};
//
//            double[] values = new double[]{3, 4, 5, 6};
//            String[][] queries = new String[][]{{"x1", "x5"}};

            public Integer findParent(int x) {
                if (x != parent[x]) {
                    int origin = parent[x];
                    parent[x] = findParent(parent[x]);
                    weight[x] *= weight[origin];
                }
                return parent[x];

            }

            public void union(int v, int w, double value) {
                Integer rootP = findParent(v);
                Integer rootQ = findParent(w);
                if (rootP == rootQ) {
                    return;
                }
                parent[rootP] = rootQ;
                weight[rootP] = weight[w] * value / weight[v];
            }
        }

        public double[] calcEquationMy(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int size = equations.size();
            Map<Node, Node> nodeMap = new HashMap<>();
            for (int i = 0; i < size; i++) {
                List<String> arr = equations.get(i);
                double value = values[i];
                String pre = arr.get(0);
                String next = arr.get(1);
                Node node = new Node(pre, next, value);
                nodeMap.put(node, node);
            }
            Node[] nodes = nodeMap.keySet().toArray(new Node[0]);
            int length = nodes.length;
            for (int i = 0; i < length; i++) {
                Node node = nodes[i];
                for (int j = i + 1; j < length; j++) {
                    Node nextNode = nodes[j];
                    if (node.isConnected(nextNode)) {
                        List<Node> nodeList = node.sameNode(nextNode);
                        for (Node node1 : nodeList) {
                            nodeMap.put(node1, node1);
                        }
                    }
                }
            }
            double[] newArr = new double[queries.size()];
            for (int i = 0; i < queries.size(); i++) {
                List<String> strings = queries.get(i);
                Node node1 = new Node(strings.get(0), strings.get(1), 0.0);
                Node node2 = new Node(strings.get(1), strings.get(0), 0.0);
                if (nodeMap.containsKey(node1)) {
                    newArr[i] = nodeMap.get(node1).value;
                } else if (nodeMap.containsKey(node2)) {
                    newArr[i] = 1 / nodeMap.get(node2).value;
                } else {
                    newArr[i] = -1.0;
                }
            }
            return newArr;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}